package elementary_alg.array;

import java.util.Arrays;

/**
 * @author : Kong Decheng
 * @date : 2021/04/02
 * @description: 旋转数组
 */
public class LC3 {

    /**
     * 方法 1：使用临时数组
     */
    public void solution_1(int[] nums, int k) {
        // 原数组长度
        int len = nums.length;
        // 1. 使用临时数组存储原数组元素
        int[] temp = new int[len];
        // 1.1 拷贝原数组元素到临时数组
        for (int i = 0; i < len; i++) {
            temp[i] = nums[i];
        }
        // 2. 计算出元素移动后的索引并移动
        // 2.1 遍历临时数组的所有元素
        for (int i = 0; i < len; i++) {
            // 计算移动后的位置，并在原数组完成移动操作
            nums[(i + k) % len] = temp[i];
        }
    }

    /**
     * 方法 2：多次反转
     * 先反转全部元素，再反转前 k 个，最后在反转剩余的
     * 如图所示：
     * https://pic.leetcode-cn.com/1610072480-yiAYFw-image.png
     */
    public void solution_2(int[] nums, int k) {
        // 数组的长度
        int len = nums.length;
        // 1. 反转全部元素, start=0, end=len-1
        reverse(nums, 0, len - 1);
        // 2. 反转前 k 个, start=0, end=k-1
        reverse(nums, 0, k - 1);
        // 3. 反转剩余的, start=k,end=len-1
        reverse(nums, k, len - 1);

    }

    /**
     * 方法 2 的反转函数
     * 把数组中 [start，end] 之间的元素两两交换,也就是反转
     *
     * @param nums  需要反转的数组
     * @param start 起始位置
     * @param end   结束位置
     */
    public void reverse(int[] nums, int start, int end) {
        // [1, 2, 3, 4, 5, 6, 7] start=0, end=2
        // [3,2,1,4,5,6,7]
        // 循环结束的条件：
        // [3,2,1,4,5,6,7] start=3,end=3
        // [3,2,1,4] start=2,end=1
        // 总结: start >= end时，结束遍历
        while (start < end) {
            // 元素交换的操作
            // 1. 先用一个临时变量保存要交换的值 3
            int temp = nums[start];
            // 2. 将结束位置的元素 1 赋值给起始位置， start++
            nums[start++] = nums[end];
            // 3. 将起始位置的元素 3 赋值给结束位置, end--
            nums[end--] = temp;
        }
    }

    /**
     * 方法3：环形旋转
     * https://pic.leetcode-cn.com/1610074370-FCoknu-image.png
     * https://pic.leetcode-cn.com/1610074381-kyhghn-image.png
     * https://pic.leetcode-cn.com/1610074389-JbBnZF-image.png
     */
    public void solution_3(int[] nums, int k) {
        // 临时变量，用来保存交换位置的元素，初始化为 nums[0]
        int hold = nums[0];
        // 移动后的位置，初始化为 0
        int index = 0;
        // 数组长度
        int length = nums.length;
        // 用来存储每个元素的访问结果，已访问：true，未访问: false
        boolean[] visited = new boolean[length];
        for (int i = 0; i < length; i++) {
            // 计算移动后的索引
            index = (index + k) % length;
            if (visited[index]) {
                //如果访问过，再次访问的话，会出现原地打转的现象，
                //不能再访问当前元素了，我们直接从他的下一个元素开始
                index = (index + 1) % length;
                hold = nums[index];
                i--;
            } else {
                //把当前值保存在下一个位置，保存之前要把下一个位置的
                //值给记录下来
                visited[index] = true;
                int temp = nums[index];
                nums[index] = hold;
                hold = temp;
            }
        }

    }
}


